//实现一个 MapSum 类，支持两个方法，insert 和 sum： 
//
// 
// MapSum() 初始化 MapSum 对象 
// void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 ke
//y 已经存在，那么原来的键值对将被替代成新的键值对。 
// int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。 
// 
//
// 
//
// 示例： 
//
// 
//输入：
//["MapSum", "insert", "sum", "insert", "sum"]
//[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
//输出：
//[null, null, 3, null, 5]
//
//解释：
//MapSum mapSum = new MapSum();
//mapSum.insert("apple", 3);  
//mapSum.sum("ap");           // return 3 (apple = 3)
//mapSum.insert("app", 2);    
//mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)
// 
//
// 
//
// 提示： 
//
// 
// 1 <= key.length, prefix.length <= 50 
// key 和 prefix 仅由小写英文字母组成 
// 1 <= val <= 1000 
// 最多调用 50 次 insert 和 sum 
// 
// Related Topics 设计 字典树 哈希表 字符串 
// 👍 108 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class MapSumPairs {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class MapSum {
            class TreeNode{
                private int val;
                TreeNode[] next;
                public TreeNode() {
                    this.val = 0;
                    this.next = new TreeNode[26];
                }
            }
            /**
             *  既然题目分类到了前缀树，那就尝试用前缀树来实现
             *  思路是这样的：
             *      map是肯定要有的，保存key和value的值
             *      前缀树的作用是保存单词，在sum时对前缀树进行遍历，如果当前前缀开始有key值就取value相加
             *      前缀树遇到的问题：无法快速找到前缀对应的所有word
             *      题解中是这样的，遍历当前节点next中的所有node，不为null就继续递归，
             *      而且节点中不再存放boolean，而是直接存放val，val直接是key对应的value就行
             *      sum的时候也是先对前缀进行遍历，遍历完前缀之后传入当前节点进行单词匹配，递归求和
             *
             *
             *  只使用map进行操作呢？这种方法好啊，就是底层是map自己实现的
             *      添加：存在则覆盖，不然则添加
             *      相加：遍历map的key，如果key.startsWith(prefix) sum+=map.get(key)
             */

            private Map<String, Integer> map;
            TreeNode root;
            public MapSum() {
                map = new HashMap<>();//方法1
                root = new TreeNode();//方法2，使用前缀树
            }

            public void insert(String key, int val) {
                if (map.containsKey(key)){
                    map.replace(key, val);
                }else {
                    map.put(key, val);
                }
            }

            public void insert2(String key, int val) {
                TreeNode node = root;
                for (char c : key.toCharArray()){
                    if (node.next[c-'a'] == null) {
                        node.next[c-'a'] = new TreeNode();
                    }
                    node = node.next[c-'a'];
                }
                node.val = val;//这里是直接进行了赋值且实现了单词标记
            }

            public int sum(String prefix) {
                int sum = 0;
                for (String s : map.keySet()){
                    if (s.startsWith(prefix)) {
                        sum += map.get(s);
                    }
                }
                return sum;
            }

            public int sum2(String prefix) {
                TreeNode node = root;
                for (char c :prefix.toCharArray()){//这里是对前缀进行匹配，匹配不到的话就直接返回0
                    if (node.next[c -'a'] == null) {
                        return 0;
                    }
                    node = node.next[c-'a'];
                }
                //能到这里说明前缀匹配完成了，现在要匹配所有的word
                return travel(node);
            }

            public int travel(TreeNode node){
                int res = node.val;//这里在insert的时候已经设置好了，如果当前是word尾的时候是可以直接拿到对应value的，否则为0
                for (TreeNode n : node.next){//遍历所有的非空节点
                    if (n!=null) {
                        res += travel(n);
                    }
                }
                return res;
            }
    }

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */
//leetcode submit region end(Prohibit modification and deletion)

}